//给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作： 
//
// 
// 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。 
// 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。 
// 
//
// 返回使字符串内所有字符 相等 需要的 最小成本 。 
//
// 反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "0011"
//输出：2
//解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。
// 
//
// 示例 2： 
//
// 
//输入：s = "010101"
//输出：9
//解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
//执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
//执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
//执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
//执行第二种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
//使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length == n <= 10⁵ 
// s[i] 为 '0' 或 '1' 
// 
//
// Related Topics 贪心 字符串 动态规划 👍 71 👎 0


package LeetCode.editor.cn;


import java.util.Arrays;

/**
 * @author ldltd
 * @date 2025-03-27 12:17:42
 * @description 2712.使所有字符相等的最小成本
 
 */
 
public class MinimumCostToMakeAllCharactersEqual {
    public static void main(String[] args) {
    //测试代码
    MinimumCostToMakeAllCharactersEqual fun = new MinimumCostToMakeAllCharactersEqual();
    Solution solution= fun.new Solution();
        System.out.println(1^1);
        System.out.println(0^1);
        System.out.println(solution.minimumCost("010101"));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //从中间开始，两边扩散，先保证中间的一样
    //分别计算变成0和变成1的成本中的最小值
    public long minimumCost1(String s) {
        if(s.length()==1) return 0;
        if(s.length()==2) return s.charAt(0)!=s.charAt(1)?1:0;
        int len = s.length();
        int[] intArray = s.chars().map(c -> c - '0').toArray();
        return Math.min(helper(len,intArray,0),helper(len,intArray,1));
    }

    private long helper(int len, int [] ar, int k) {
        long count=0;
        long res=0;
        for (int i = (len-1)/2; i >=0 ; i--) {
            while (i>=0&&(ar[i]^(count%2))==k){
                    i--;
            }
            if(i>=0){
                res+=(i+1);
                count+=1;
            }
        }
         count=0;
        for (int i = (len-1)/2+1; i <len ; i++) {
            while (i<len&&(ar[i]^(count%2))==k){
                i++;
            }
            if(i<len){
                res+=(len-i);
                count+=1;
            }
        }
        return res;
    }
    /*动态规划，维护一个前缀变成0 或者1的最小成本，后缀变成0和1的最小成本
    定义suf[i][0]标识从i开始后缀变成0的最小成本
    pre[i][0]标识从0到i变成0的最小成本
    如果s[i]==1，则suf[i][1]=suf[i+1][1]
                则suf[i][0]=suf[i+1][1]+(n-i)
    如果s[i]==0，则suf[i][1]=suf[i=1][0]+(n-i)
                则suf[i][0]=suf[i=1][1]
    pre[i][0]和pre[i][i]转移过程类似，遍历所有i
    求解min(pre[i][0]+suf[i+1][0],pre[i][1]+suf[i+1][1])最小值
    * */

    public long minimumCost(String s) {
        int n = s.length();
        long[][] suf = new long[n + 1][2];
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '1') {
                suf[i][1] = suf[i + 1][1];
                suf[i][0] = suf[i + 1][1] + (n - i);
            } else {
                suf[i][1] = suf[i + 1][0] + (n - i);
                suf[i][0] = suf[i + 1][0];
            }
        }
        //第二次遍历前缀成本的时候就可以用滚动数组节约空间了
        long[] pre = new long[2];
        long res = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                pre[0] = pre[1] + i + 1;
            } else {
                pre[1] = pre[0] + i + 1;
            }
            res = Math.min(res, Math.min(pre[0] + suf[i + 1][0], pre[1] + suf[i + 1][1]));
        }
        return res;
    }


    /*我们并不关心字符最终会变成 0 还是 1，只要它们相等即可。因此需要关注每对相邻字符的相等关系。一次操作有如下性质：
一次操作可以且一定改变一对相邻字符的关系。
对于两个相邻且不相等的字符，必须经过一次操作才能使它们相等。
对某两个相邻字符操作结束后，左侧和右侧所有的相邻字符的相等关系不变。
因此，我们只需枚举所有的相邻字符，对不同的进行操作。操作时选择成本更小的一侧，其总和就是答案。
        */

    public long minimumCost2(String s) {
        int n = s.length();
        long res = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                //可以从左侧或者右侧操作
                res += Math.min(i, n - i);
            }
        }
        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
